/*************************************************************************
	> File Name: permutation.cpp
	> Author: likang
	> Mail: likang@ict.ac.cn
	> Created Time: 一  8/14 14:54:49 2017
 ************************************************************************/

// 排列
// 组合

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

void swap(int* arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void permutation(int* arr, int low, int high) {

    if (low == high) {
        for (int i = 0; i <= high; ++i) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = low; i <= high; ++i) {
        swap(arr, i, low);
        permutation(arr, low + 1, high);
        swap(arr, i, low);
    }
}

// 去除重复的排列
//当交换 p, q 两个元素时，判断 arr[q] 是否在 arr[p,q) 中出现
//
bool isSwap(int* arr, int p, int q) {
    for (int i = p; i < q; ++i) {
        if (arr[q] == arr[i]) {
            return false;
        }
    }    
    return true;
}

void ddpermutation(int* arr, int low, int high) {

    if (low == high) {
        for (int i = 0; i <= high; ++i) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = low; i <= high; ++i) {
        if (isSwap(arr, low, i)) {
            swap(arr, i, low);
            ddpermutation(arr, low + 1, high);
            swap(arr, i, low);
        }
    }
}

void combination(int* arr, int low, int high, int m, int index, int* data) {
    
    if (index == m) {
        for (int i = 0; i < m; ++i) {
            cout << data[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = low; i <= high && high - i + 1 >= m - index; ++i) {
        data[index] = arr[i];
        combination(arr, i + 1, high, m, index + 1, data);
    }
}
// 输出所有的组合，利用位图的方法
//
void combinationAll() {
    string s = "abcd";
    vector<string> res;
    int len = s.size();
    int j;
    int index;
    string sub;

    for (int i = 1; i < pow(2, len); ++i) {

        j = i;
        index = 0;
        sub = "";

        while (j) {
            if (j & 1) {
                sub += s[index];
            }
            ++index;
            j >>= 1;
        }
        res.push_back(sub);
    }

    for (auto it = res.begin(); it != res.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}
// 去除重复的组合
// 将所有的组合用 set 保存起来、、、

void ddcombination(vector<int>& arr, int low, int high, int m, int index, int* data) {

}

int main(void) {
    int a[] = {1, 2, 2};
    cout << "排列......" << endl;
    permutation(a, 0, 2);
    cout << "去除重复的排列......" << endl;
    ddpermutation(a, 0, 2);
    int data[2];
    cout << "组合......" << endl;
    combination(a, 0, 2, 2, 0, data);
    cout << "全部组合......" << endl;
    combinationAll();
    cout << "去除重复的组合......" << endl;
    return 0;
}
